#include "Graph.h"
#include <queue>
#include <unordered_set>

queue<GraphEdge*> Prim(Graph* g)
{
    priority_queue<GraphEdge*, vector<GraphEdge*>, EdgeCmp> edgeSet;//用于取找到的最小边
    unordered_set<int> findNodes;//记录已经走过的节点
    queue<GraphEdge*> results;//最终选中的边
    for (auto n : g->nodeSet)
    {
        // auto n = g->nodeSet[1]; //可以将for循环换成这个，for循环是考虑森林的情况
        if(findNodes.count(n->value) == 0)//记录找到的新点
        {
            findNodes.insert(n->value);
            for(auto e : n->edges)//记录新点连接的新边
            {
                edgeSet.push(e);
            }
            while(!edgeSet.empty())//找出一条最小边
            {
                auto e = edgeSet.top();
                edgeSet.pop();
                auto to = e->to;
                if(findNodes.count(to->value) == 0)//如果边所通向的点没找过
                {
                    findNodes.insert(to->value);//记录该点
                    results.push(e);
                    for(auto nextEdge:to->edges)//记录该点的边（可能会重复，影响不大）
                        edgeSet.push(nextEdge);
                }
            }
        }
    }
    return results;
}